package 链表;

public class 反转链表第i到j之间的节点 {

    public static void main(String[] args) {
        ListNode node = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5)))));
//        while (node != null) {
//            System.out.print(node.val);
//            System.out.print(",");
//            node = node.next;
//        }
        反转链表第i到j之间的节点 反转链表第i到j之间的节点 = new 反转链表第i到j之间的节点();
        ListNode listNode = 反转链表第i到j之间的节点.reverseBetween(node,2,3);
        while (listNode != null) {
            System.out.print(listNode.val);
            System.out.print(",");
            listNode = listNode.next;
        }
    }

    public ListNode reverseBetween(ListNode head, int i, int j) {
        // 创建虚拟头节点，方便处理边界情况，使得无论对链表头部还是中间部分操作逻辑更统一
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // prev指针用于定位到需要反转部分的前一个节点
        ListNode prev = dummy;
        ListNode end = dummy;
        // 移动prev指针到第i - 1个节点的位置（因为索引从1开始算，所以移动i - 1次）
        for (int k = 0; k < i - 1; k++) {
            prev = prev.next;
        }
        // start指向第i个节点，也就是需要反转部分的起始节点
        ListNode start = prev.next;
        for (int q = 0; q < j; q++) {
            end = end.next;
        }
        end = end.next;
        // 接下来进行节点反转操作，类似普通链表反转的思路
        ListNode n = reverse(start,end);
        prev.next = n;
        while (prev.next != null){
            prev = prev.next;
        }
        prev.next = end;
        // 返回虚拟头节点的下一个节点，即处理后的链表头节点
        return dummy.next;
    }


    /**
     * 左闭右开
     * @param a
     * @param b
     * @return
     */
    private ListNode reverse(ListNode a,ListNode b) {
        ListNode pre = null;
        ListNode cur = a;
        ListNode nxt;

        while (cur != b) {
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
}
